package com.exercises;

/**
 *  并归排序
 */
class Exercise179 {
    public static void main(String[] args) {
        System.out.println(largestNumber(new int[]{0, 9, 8, 7, 6, 5, 4, 3, 2, 1}));
    }


    public static String largestNumber(int[] nums) {
        String[] arrays = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arrays[i] = String.valueOf(nums[i]);
        }
        sort(arrays);
        StringBuilder stringBuilder = new StringBuilder();
        for (String str : arrays) {
            stringBuilder.append(str);
        }
        String result = stringBuilder.toString();
        return result.startsWith("0") ? "0" : result;
    }


    public static void sort(String[] arr) {
        sort(arr, 0, arr.length - 1, new String[arr.length]);
    }

    public static void sort(String[] arr, int from, int to, String[] temp) {
        if (to > from) {
            int mid = (from + to) / 2;
            sort(arr, from, mid, temp);
            sort(arr, mid + 1, to, temp);
            merge(arr, from, mid, to, temp);
        }
    }

    private static void merge(String[] arr, int from, int mid, int to, String[] temp) {
        int i = from, j = mid + 1;
        int add = 0;
        while (i <= mid || j <= to) {
            String a = i <= mid ? arr[i] : "0";
            String b = j <= to ? arr[j] : "0";

            if (Long.parseLong(a + b) > Long.parseLong(b + a)) {
                temp[from + add] = a;
                i++;
            } else if (Long.parseLong(a + b) < Long.parseLong(b + a)) {
                temp[from + add] = b;
                j++;
            } else {
                temp[from + add] = a;
                if (i <= mid) i++;
                else j++;
            }
            add++;
        }
        for (int k = from; k <= to; k++) {
            arr[k] = temp[k];
        }
        System.out.println(String.join(",", arr));
    }


}

